#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define RED(msg) "\033[0;1;31m" msg "\033[0m"
#define YELLOW(msg) "\033[0;1;33m" msg "\033[0m"
#define BASE 26

typedef struct Node {
    const char *str;
    struct Node *next[BASE], *fail;
} Node;

typedef struct Queue {
    Node **data;
    int head, tail;
} Queue;

Queue *initQueue(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (Node **)malloc(sizeof(Node *) * n);
    q->head = q->tail = 0;
    return q;
}

int empty(Queue *q) {
    return q->tail - q->head == 0;
}

Node *front(Queue *q) {
    return q->data[q->head];
}

void push(Queue *q, Node *node) {
    q->data[q->tail++] = node;
    return ;
}

void pop(Queue *q) {
    if (empty(q)) return ;
    q->head += 1;
    return ;
}

void clearQueue(Queue *q) {
    if (q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}

int node_cnt = 0;
Node *getNewNode() {
    node_cnt += 1;
    Node *p   = (Node *)malloc(sizeof(Node));
    p->str    = NULL;
    p->fail   = NULL;
    memset(p->next, 0, sizeof(Node *) * BASE);
    return p;
}

inline int ind(char ch) {
    return ch - 'a';
}

const char *copyStr(const char *s) {
    int n = strlen(s);
    char *buff = (char *)malloc(n + 1);
    strcpy(buff, s);
    return buff;
}

void insert(Node *root, const char *s) {
    Node *p = root;
    for (int i = 0; s[i]; i++) {
        if (p->next[ind(s[i])] == NULL) p->next[ind(s[i])] = getNewNode();
        p = p->next[ind(s[i])];
    }
    p->str = copyStr(s);
    return ;
}

void clear(Node *root) {
    if (root == NULL) return ;
    for (int i = 0; i < BASE; i++) {
        clear(root->next[i]);
    }
    if (root->str) free((char *)root->str);
    free(root);
    return ;
}

void initBuildFailQueue(Node *root, Queue *q) {
    root->fail = NULL;
    for (int i = 0; i < BASE; i++) {
        if (root->next[i] == NULL) continue;
        root->next[i]->fail = root;
        push(q, root->next[i]);
    }
    return ;
}

void build_fail(Node *root) {
    Queue *q = initQueue(node_cnt);
    initBuildFailQueue(root, q);
    while (!empty(q)) {
        Node *p = front(q);
        for (int i = 0; i < BASE; i++) {
            if (p->next[i] == NULL) continue;
            Node *k = p->fail;
            while (k != root && k->next[i] == NULL) k = k->fail;
            if (k->next[i] != NULL) k = k->next[i];
            p->next[i]->fail = k;
            push(q, p->next[i]);
        }
        pop(q);
    }
    clearQueue(q);
    return ;
}

void match_ac(Node *root, const char *s) {
    Node *p = root, *q;
    for (int i = 0; s[i]; i++) {
        while (p != root && p->next[ind(s[i])] == NULL) p = p->fail;
        if (p->next[ind(s[i])]) p = p->next[ind(s[i])];
        printf("input %c : %p\n", s[i], p);
        q = p;
        while (q) {
            if (q->str != NULL) printf(YELLOW("find ") RED("%s\n"), q->str);
            q = q->fail;
        }
    }
    return ;
}

int main() {
    int n;
    char s[100];
    scanf("%d", &n);
    Node *root = getNewNode();
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        insert(root, s);
    }
    printf("build trie done...\n");
    build_fail(root);
    printf("build fail pointer done...\n");
    scanf("%s", s);
    printf("match ac start : \n");
    match_ac(root, s);
    return 0;
}

